package demo.sort;

public class QuickSort {
    public static void main(String[] args) {
        QuickSort q = new QuickSort();
        int[] src = new int[]{52, 2, 8, 7, 12, 99, 88,1,3,4,6,8};
        q.quickSort(src);
    }

    public int[] quickSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return arr;
        }
        quickSort(arr, 0, arr.length - 1);
        return arr;
    }

    public void quickSort(int[] arr, int l, int r) {
        if (l < r) {
            int partitionIndex = partition(arr, l, r);
            quickSort(arr, l, partitionIndex - 1);
            quickSort(arr, partitionIndex + 1, r);
        }
    }

    public int partition(int[] arr, int l, int r) {
        int point = arr[l];
        int[] cp = new int[r - l + 1];
        int i = l + 1;
        int min = 0, max = cp.length - 1;
        for (; i <= r; i++) {
            if (arr[i] >= point) {
                cp[max--] = arr[i];
            } else {
                cp[min++] = arr[i];
            }
        }
        cp[min] = point;
        System.arraycopy(cp, 0, arr, l, r - l + 1);
        return min + l;
    }
}
